#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#define MAXTABLESIZE 1000000 /* 散列表最大规模 */
#define ERROR -1
typedef char* ElementType;
typedef struct LNode *PtrtoLNode; /* 散列表单元类型 */
struct LNode
{
    char Data[51];
    int Count1, Count2;
    PtrtoLNode Next;
};
typedef PtrtoLNode Position;
typedef PtrtoLNode List;
typedef struct TblNode *HashTable; /* 散列表类型 */
struct TblNode /* 散列表结点定义 */
{
    int TableSize; /* 表的长度 */
    List Heads;   /* 指向链表头节点的数组 */
};
struct wordlist
{
    char Data[51];
    int Count1, Count2;
};
typedef struct wordlist Cell;
typedef Cell *MaxHeap;
const double eps = 1e-9;
int cmp(double a,double b)
{
	return (a-b)<-eps ? -1:(a-b)>eps;
}

HashTable CreateTable(int TableSize);
int NextPrime(int N);
Position Find(HashTable H, ElementType Key);
int Insert(HashTable H, ElementType Key);
int Hash(char *Key, int TableSize);
void GetAWord(FILE *fp, ElementType Word);
void PercDown1(MaxHeap H, int p, int Size);
void BuildHeap1(MaxHeap H, int Size);
void PercDown2(MaxHeap H, int p, int Size);
void BuildHeap2(MaxHeap H, int Size);
int Cmp1(const void *a, const void *b);
int Cmp2(const void *a, const void *b);
void Show(HashTable H, int n, FILE *fp);

int main()
{
    int TableSize = 535727, N;
    scanf("%d", &N);
    HashTable H = CreateTable(TableSize);
    HashTable STOP = CreateTable(307);
    FILE *DIC, *ST, *ART1, *ART2, *OUT;
    if((DIC = fopen("dictionary.txt","r")) == NULL)
    {
        printf("The file do not exist.\n");
        return -1;
    }
    if((ST = fopen("stopwords.txt","r")) == NULL)
    {
        printf("The file do not exist.\n");
        return -1;
    }
    if((ART1 = fopen("article1.txt","r")) == NULL)
    {
        printf("The file do not exist.\n");
        return -1;
    }
    if((ART2 = fopen("article2.txt","r")) == NULL)
    {
        printf("The file do not exist.\n");
        return -1;
    }
    OUT = fopen("results.txt","w");
    /* 读取词典 */
    char ch[100];
    while(fscanf(DIC, "%s", ch)!=EOF)
        Insert(H, ch);
    /* 读取并删除停用词 */
    while(fscanf(ST, "%s", ch)!=EOF)
        Insert(STOP, ch);
    memset(ch, '\0', sizeof(ch));
    /* 读取文章一 */
    while(!feof(ART1))
    {        
        GetAWord(ART1, ch);
        Position P = Find(H, ch), Q = Find(STOP, ch); //有可能返回个空位置
        if(P && !Q) P->Count1++;
        memset(ch, '\0', sizeof(ch));
    }
    /* 读取文章二 */
    while(!feof(ART2))
    {        
        GetAWord(ART2, ch);
        Position P = Find(H, ch), Q = Find(STOP, ch);
        if(P && !Q) P->Count2++;
        memset(ch, '\0', sizeof(ch));
    }
    /* 输出结果 */
    Show(H, N, OUT);
    return 0;
}

void GetAWord(FILE *fp, ElementType ch)
{
    char c;
    c = fgetc(fp);
    int len = 0;
    while(!feof(fp))
    {            
        if(isalpha(c)) 
            ch[len++] = tolower(c); // tolower会把大写字母变成小写字母，但不会改变小写字母，所以大小写可以放一起
        else break;
        c = fgetc(fp);
    }
    ch[len] = '\0';
}

int NextPrime(int N)
{
    if(N == 1 || N == 2) return 2;
    int i, p = (N%2)? N : N+1;
    while(p <= MAXTABLESIZE) 
    {
        for(i=(int)sqrt(p);i>2;i--)
            if(!(p%i)) break;
        if(i == 2) break;
        else  p += 2;
    }
    return p;
}

HashTable CreateTable(int TableSize)
{
    HashTable H;
    int i;
    H = (HashTable)malloc(sizeof(struct TblNode));
    H->TableSize = TableSize; 
    /* 以下分配链表头结点数组 */
    H->Heads = (List)malloc(H->TableSize*sizeof(struct LNode));
    /* 初始化表头结点 */
    for(i=0;i<H->TableSize;i++)
    {
        H->Heads[i].Data[0] = '\0';
        H->Heads[i].Count1 = H->Heads[i].Count2 = 0;
        H->Heads[i].Next = NULL;
    }
    return H;
}

int Hash(char *Key, int TableSize)
{
    int h = 0; /* 散列函数值，初始化为0 */
    while (*Key != '\0')
        h = (h*131 + *Key++) % TableSize;
    return h;
}

Position Find(HashTable H, ElementType Key)
{
    Position P;
    int Pos; 
    Pos = Hash(Key, H->TableSize); /* 初始散列位置 */
    P = H->Heads[Pos].Next; /* 从该链表的第1个结点开始 */
    /* 当未到表尾，并且Key未找到时 */ 
    while(P && strcmp(P->Data, Key))
        P = P->Next;
    return P; /* 此时P或者指向找到的结点，或者为NULL */
}

int Insert(HashTable H, ElementType Key)
{
    Position P, NewCell;
    int Pos;
    P = Find(H, Key);
    if(!P) /* 关键词未找到，可以插入 */
    {
        NewCell = (Position)malloc(sizeof(struct LNode));
        NewCell->Count1 = NewCell->Count2 = 0;
        strcpy(NewCell->Data, Key);
        Pos = Hash(Key, H->TableSize); /* 初始散列位置 */        
        NewCell->Next = H->Heads[Pos].Next;/* 将NewCell插入为H->Heads[Pos]链表的第1个结点 */
        H->Heads[Pos].Next = NewCell; 
        return 1;
    }
    else /* 关键词已存在 */
        return 0;
}

void PercDown1(MaxHeap A, int p, int N)
{
    int Parent, Child;
    Cell X;
    X = A[p]; /* 取出根结点存放的值 */
    for(Parent=p; (Parent*2+1)<N; Parent=Child) 
    {
        Child = Parent * 2 + 1;
        if(Child != N-1 && ((A[Child].Count1 > A[Child+1].Count1) || (A[Child].Count1 == A[Child+1].Count1 && strcmp(A[Child].Data, A[Child+1].Data) < 0) ))
            Child++;  /* Child指向左右子结点的较小者 */
        if(X.Count1 < A[Child].Count1 || (X.Count1 == A[Child].Count1 && strcmp(X.Data, A[Child].Data) > 0)) break; /* 找到了合适位置 */
        else  /* 下滤X */
            A[Parent] = A[Child];
    }
    A[Parent] = X;
}

void BuildHeap1(MaxHeap H, int Size)
{
    int i; 
    for(i=Size/2-1;i>=0;i--)
        PercDown1(H, i, Size);
}

void PercDown2(MaxHeap A, int p, int N)
{
    int Parent, Child;
    Cell X;
    X = A[p]; /* 取出根结点存放的值 */
    for(Parent=p; (Parent*2+1)<N; Parent=Child) 
    {
        Child = Parent * 2 + 1;
        if(Child != N-1 && ((A[Child].Count2 > A[Child+1].Count2) || (A[Child].Count2 == A[Child+1].Count2 && strcmp(A[Child].Data, A[Child+1].Data) < 0) ))
            Child++;
        if(X.Count2 < A[Child].Count2 || (X.Count2 == A[Child].Count2 && strcmp(X.Data, A[Child].Data) > 0)) break; /* 找到了合适位置 */
        else  /* 下滤X */
            A[Parent] = A[Child];
    }
    A[Parent] = X;
}

void BuildHeap2(MaxHeap H, int Size)
{
    int i; 
    for(i=Size/2-1;i>=0;i--)
        PercDown2(H, i, Size);
}

int Cmp1(const void *a, const void *b)
{
    int BOOL = ((Cell *)b)->Count1 - ((Cell *)a)->Count1;
    return (BOOL!=0 ? BOOL : strcmp(((Cell *)a)->Data, ((Cell *)b)->Data) );
}

int Cmp2(const void *a, const void *b)
{
    int BOOL = ((Cell *)b)->Count2 - ((Cell *)a)->Count2;
    return (BOOL!=0 ? BOOL : strcmp(((Cell *)a)->Data, ((Cell *)b)->Data) );
}

void Show(HashTable H, int n, FILE *fp)
{
    int total_freq1 = 0, total_freq2 = 0, freq1 = 0, freq2 = 0;
    Cell art1[n], art2[n];
    memset(art1, 0, sizeof(art1));
    memset(art2, 0, sizeof(art2));
    int cnt1 = 0, cnt2 = 0;
    Position L;
    for(int i=0;i<H->TableSize;i++)
    {
        L = H->Heads[i].Next;
        while(L)
        {
            if(L->Count1 > 0)
            {
                if(cnt1 < n)
                {
                    strcpy(art1[cnt1].Data, L->Data);
                    art1[cnt1].Count1 = L->Count1;
                    cnt1++;
                }
                else
                {
                    if(cnt1 == n)
                    {
                        cnt1++;
                        BuildHeap1(art1, n);
                    }
                    if(L->Count1 > art1[0].Count1 || (L->Count1 == art1[0].Count1 && strcmp(L->Data,art1[0].Data)<0) )
                    {
                        strcpy(art1[0].Data, L->Data);
                        art1[0].Count1 = L->Count1;
                        PercDown1(art1, 0, n);
                    }
                }
            }
            if(L->Count2 > 0)
            {
                if(cnt2 < n)
                {
                    strcpy(art2[cnt2].Data, L->Data);
                    art2[cnt2].Count2 = L->Count2;
                    cnt2++;
                }
                else
                {
                    if(cnt2 == n)
                    {
                        cnt2++;
                        BuildHeap2(art2, n);
                    }
                    if(L->Count2 > art2[0].Count2 || (L->Count2 == art2[0].Count2 && strcmp(L->Data,art2[0].Data)<0) )
                    {
                        strcpy(art2[0].Data, L->Data);
                        art2[0].Count2 = L->Count2;
                        PercDown2(art2, 0, n);
                    }
                }
            }
            L = L->Next;
        }
    }
    if(cnt1 > n) cnt1--; if(cnt2 > n) cnt2--;
    qsort(art1, cnt1, sizeof(Cell), Cmp1); qsort(art2, cnt2, sizeof(Cell), Cmp2);
    for(int i=0;i<cnt1;i++)
        for(int j=0;j<cnt2;j++)
            if(strcmp(art1[i].Data, art2[j].Data) == 0)
            {
                freq1 += art1[i].Count1;
                freq2 += art2[j].Count2;
            }
    for(int i=0;i<n;i++)
    {
        total_freq1 += art1[i].Count1;
        total_freq2 += art2[i].Count2;
    }
    double Sim, Pro1 = (double)freq1/(double)total_freq1, Pro2 = (double)freq2/(double)total_freq2;
    if(cmp(Pro1, Pro2)>0) Sim = Pro2/Pro1;
    else Sim = Pro1/Pro2;
    printf("%.5f\n", Sim);
    fprintf(fp, "%.5f\n\n", Sim);
    for(int i=0;i<cnt1;i++)
        fprintf(fp, "%s %d\n", art1[i].Data, art1[i].Count1);
    fprintf(fp, "\n");
    for(int i=0;i<cnt2;i++)
        fprintf(fp, "%s %d\n", art2[i].Data, art2[i].Count2);
}